package leetcode.code0983;

/**
 *
 * 【瓦片】983. 最低票价 Java 88.34% 记忆化搜索 `function(int index, int costIndex)`
 * `index`索引那天，决定以`costIndex`方式去旅行花费比较小。
 *
 * 主函数，`costIndex`为0，第0天的累计花费为0。
 *
 * `costIndex`参数来自累加消费。但是消费数值不利于dp，因此用索引代替。消费中并没有0消费的情况，因此增加第0种消费。其余三种在此基础上做-1处理。
 */
public class Solution extends Solution983 {

	/**
	 * 执行用时：3 ms, 在所有 Java 提交中击败了12.62%的用户
	 *
	 * 内存消耗：37.7 MB, 在所有 Java 提交中击败了18.74%的用户
	 *
	 * 通过测试用例：69 / 69
	 */
	@Override
	public int mincostTickets(int[] days, int[] costs) {
		int len = days.length;
		Integer[][] dp = new Integer[len + 1][4];
		for (int j = 3; j >= 0; j--) {
			dp[len][j] = j == 0 ? 0 : costs[j - 1];
		}
		for (int i = len - 1; i >= 0; i--) {
			for (int j = 3; j >= 0; j--) {
				int ans = dp[i + 1][1];
				int index7 = i;
				int index30 = i;
				for (int k = i; k < days.length; k++) {
					if (days[k] <= days[i] + 6) {
						index7 = k;
						index30 = k;
					} else if (days[k] <= days[i] + 29) {
						index30 = k;
					} else {
						break;
					}
				}
				ans = Math.min(ans, dp[index7 + 1][2]);
				ans = Math.min(ans, dp[index30 + 1][3]);
				dp[i][j] = j == 0 ? ans : ans + costs[j - 1];
			}
		}
		return dp[0][0];
	}

	private int function(int[] days, int[] costs, int i, int j, Integer[][] dp) {
		if (days.length == i) {
			return costs[j - 1];
		}
		if (dp[i][j] != null) {
			return dp[i][j];
		}
		int ans = this.function(days, costs, i + 1, 1, dp);
		int start = days[i];
		int end7 = start + 6;
		int end30 = start + 29;
		int index7 = i;
		int index30 = i;
		for (int k = i; k < days.length; k++) {
			if (days[k] <= end7) {
				index7 = k;
				index30 = k;
			} else if (days[k] <= end30) {
				index30 = k;
			} else {
				break;
			}
		}
		ans = Math.min(ans, this.function(days, costs, index7 + 1, 2, dp));
		ans = Math.min(ans, this.function(days, costs, index30 + 1, 3, dp));
		ans = j == 0 ? ans : ans + costs[j - 1];
		dp[i][j] = ans;
		return ans;
	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();
	}

}
